package com.voilet.interview.data.map;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created by kan212 on 2019/3/27.
 */

public class MyHashMap<K, V> implements MyMap<K, V> {

    //数组的初始化长度
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //阈值比例
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    int defaultInitSize;

    float defaultLoadFactor;

    int entryUseSize;

    Entry<K, V>[] table = null;

    public MyHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int defaultInitialCapacity, float defaultLoadFactor) {
        if (defaultInitialCapacity < 0) {
            throw new IllegalArgumentException("");
        }
        if (defaultInitialCapacity < 0) {
            throw new IllegalArgumentException("");
        }
        this.defaultInitSize = defaultInitialCapacity;
        this.defaultLoadFactor = defaultLoadFactor;
        table = new Entry[this.defaultInitSize];
        PriorityQueue<String> priorityQueue = new PriorityQueue<String>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return 0;
            }
        });
    }

    @Override
    public V put(K k, V v) {
        V oldValue = null;
        //判断是否需要扩容
        //扩容完成之后需要重新散列
        if (entryUseSize >= defaultInitSize * defaultLoadFactor) {
            resize(2 * defaultInitSize);
        }
        //得到hash值，计算出数组中的位置
        int index = hash(k) & (defaultInitSize - 1);
        //如果这个位置不存在就创建链表
        if (table[index] == null) {
            table[index] = new Entry<>(k,v,null);
            ++ entryUseSize;
        }else {
            //位置存在就比较并且添加到链表尾部
            Entry<K,V> entry = table[index];
            Entry<K,V> e = entry;
            while (e != null){
                // 如果发现已有该键值，则存储新的值，并返回原始值
                if (k == e.getKey() || k.equals(e.getKey())){
                    oldValue = e.value;
                    e.value = v;
                    return oldValue;
                }
                e = e.next;
            }
            table[index] = new Entry<>(k,v,entry);
            ++ entryUseSize;
        }
        return oldValue;
    }

    private int hash(K k) {
        int hashcode = k.hashCode();
        hashcode ^= (hashcode >>> 20) ^ (hashcode >>> 12);
        return hashcode ^ (hashcode >>> 7) ^ (hashcode >>> 4);
    }

    //扩容并且重新散列
    private void resize(int i) {
        Entry[] newTable = new Entry[i];
        //改变数组大小
        defaultInitSize = i;
        entryUseSize = 0;
        reHash(newTable);
    }

    //重新散列
    private void reHash(Entry<K, V>[] newTable) {
        //遍历链表，吧所有的元素添加进去
        List<Entry<K, V>> entryList = new ArrayList<>();
        for (Entry<K, V> entry : table) {
            if (null != entry) {
                do {
                    entryList.add(entry);
                    entry = entry.next;
                } while (entry.next != null);
            }
        }
        //所有元素保存到列表中之后重新换数组
        if (newTable.length > 0) {
            table = newTable;
        }
        //在重新插入进入hashmap中
        for (Entry<K, V> entry : entryList) {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public V get(K k) {
        StringBuilder s;
        int index = hash(k) & (defaultInitSize - 1);
        if (table[index] == null){
            return null;
        }else {
            Entry<K,V> entry = table[index];
            do {
                if (k == entry.getKey() || k.equals(entry.getKey())){
                    return entry.value;
                }
                entry = entry.next;
            }while (entry != null);
        }
        return null;
    }


    //单链表实现
    class Entry<K, V> implements MyMap.Entry<K, V> {

        K key;
        V value;
        Entry<K, V> next;

        public Entry() {

        }

        public Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }
    }
}
